1. Field of the Invention
The present invention relates generally to data flow a processor for information processor. In particular, the invention is directed to a data flow type information processor for processing data in accordance with a data flow program.
2. Description ,of the Prior Art
FIG. 1 illustrated a block diagram of a basic processor (Japanese Patent Laying Open No. 344439/1978) by Jack B. Dennis, which is an example of a conventional data flow type information processor. In FIG. 1, an active memory 1 stores at least one active instruction record. An arithmetic unit 2 handles a signal associated with data calculation. A decision unit 3 handles a signal associated with selection. A control identity unit 4 handles a signal associated with program control. A first arbitration network 5 transfers a signal representing information packet from the active memory 1 to the arithmetic unit 2 and the decision unit 3. A second arbitration network 6 transfers a signal representing an information packet from the active memory 1 to the control identity unit 4. The first control network 7 transfers the information packet from the decision unit 3 to the active memory 1. The second control network 8 transfers the information packet from the control identity unit 4 to the active memory 1. A distribution network 9 transfers a signal data packet from the arithmetic unit 2 to the active memory 1.
Meanwhile, basic data flow language comprises actor, link, and arc. A token flowing over the arc of the data flow program described in the basic data flow language comprises a data token, a Boolean control token and a control token. The data token represents numerical data. The Boolean control token takes the value of "truth" or "false". The control token has a control value for controlling the flow of the data token. The actor of the basic data flow language is shown in FIGS. 2(a), 2(c), 2(d), 2(e) and 2(f). An operator receives data token as an input, applies a predetermined operation to the input data token and then provides the operation result as a data token. A decision element receives data token as an input, applies to the input data token an operation for deciding a predetermined condition, and then provides the decision result as a Boolean control token of "truth" or "false". T gate receives data token and Boolean control token as inputs and provides the inputted data token intact if the inputted Boolean control token is "truth" and simultaneously produces control token and provides the same. On the other hand, the T gate produces only control token when the inputted Boolean control token is "false" and then outputs the produced token and absorbs the inputted data token. F gate receives data token and Boolean control token as inputs, just like the T gate, and provides the inputted data token intact if the inputted control token is "false" and at the same time, produces control token and provides the same as outputs. On the other hand, the F gate produces only control token when the inputted Boolean control token is "truth", and provides the produced token as an output and absorbs the inputted data token. Merge receives two data tokens, that is, Boolean control token and control token as inputs and provides as output the input data token on the T side intact when the inputted Boolean control token is "truth" and the inputted data token on the F side intact when "false". The Boolean operator receives, as input, Boolean control token or control token and, after a predetermined Boolean operation, provides, as an output, "truth" or "false" Boolean control token or control token. Link of the basic flow language is shown in FIGS. 2(g) and 2(h). Data link serves to send out a single inputted data token intact to one or more output arc by copying. A control link serves to send out a single inputted Boolean control token or control token to one or more output arcs by copying.
FIG. 3 shows a descriptive example of the data flow program by the basic data flow language. In FIG. 3, a program containing a while type loop structure shown in FIG. 4, that is, a loop structure of a type in which termination of the loop is determined before the execution of processing of a loop body, is described by the basic data flow language. In FIG. 3, a large solid circle F represents Boolean control token (false) in an initial state and a large solid circle C represents control token in an initial state. An execution of data flow program shown in FIG. 3 is started when data token corresponding to x or y arrives at the merge. After arrival of data token corresponding to x and y at the merge, comparison of x and y and operation of (x - y) are executed. The comparison result of x and y is sent to the T gate, the F gate and the merge, as a "truth" or "false" Boolean control token. If the comparison result is "truth", the control token is sent out to all of the merges for repetition of loop processing. This occurs after control tokens outputted from all of the T gates and F gates gather, that is, after processing of all of the T gates and F gates is completed. If the comparison result is "false" , the data tokens corresponding to x and n are outputted from the F gates, which become the output data of the loop structure. Further, after the control tokens outputted from all of the T gates and F gates gather, that is, after processing of all of the T gates and F gates are completed, the control tokens are sent out to all of the merges and arrival of the data token corresponding to the next x or next y at the merges is awaited. Then, as soon as the data token arrives at the merges, the same processing as that at the time of arrival of data token corresponding to said x and y is repeated.
If and when the data flow program containing a loop structure is executed in the above described conventional example, processing of a loop body is repeated with respect to the present input data set to the loop structure or the loop processing is initiated with respect to the next input data set to the loop structure after completion of processing of all of the T gates and F gates forming the loop structure is detected (referred to as "a synchronization is obtained" hereinafter). More particularly, it is assured that execution of all of the actors included in the loop structure is completed before the next repetition with respect to the present input data set or a loop processing with respect to the next input data set is started. This is because, if the above described assurance is not obtained, the processing status in each path forming a loop in the loop structure is different, so that a token in a different cycle is likely to erroneously form a token pair.
In an execution control system based on an unwound manner of the loop structure shown in FIG. 3, in order to detect completion of a cycle in the loop structure an, OR operation is repeated with respect to all of the control tokens outputted from the T gates and F gates forming the loop structure. The number of OR operations required for detecting completion of one cycle in the loop structure is (n+m-1), wherein n and m (1.ltoreq.m.ltoreq.n) denote the number of input and outputs to the loop structure. In addition, OR operators of more than log (n+m-1) which are arranged in series are required for achieving all of OR operations. In this case, the base of logarithm is 2, and thus, a minimum number of stages is required if the OR operators are arranged in a dichotomizing tree structure. The OR operators required for detecting completion of one cycle are required in execution of a data flow program having the above described loop structure. This decreases efficiency of program execution, resulting in an increase of execution time of program.
In addition, the above described execution control system employs a control mechanism in which by disposing the merges shown in FIG. 2 (e) in the input portion of the loop structure, the loop processing with respect to the next input data set to the loop structure is started after the loop processing with respect to the present input data set to the loop structure is completed. More particularly, the next input data set is caused to wait at the input portion of the loop structure until the loop processing with respect to the present input data set is completed. As a result, the parallelism inherent to the program is restricted. Thus, efficiency of program execution is decreased.
In addition, since three kinds of tokens, that is, data token, Boolean control token and control token are used as a token, and a processing units and networks are prepared for each token, the execution control system becomes complicated and the amount of hardware is increased.